马尔可夫决策过程

马尔可夫链是什么？

马尔可夫链是一种特殊类型的随机过程，它具有一个关键特性：马尔可夫性质。这意味着系统的未来状态仅依赖于当前状态，而与之前的历史状态无关。因此，马尔可夫链可以被视为随机过程的一个子类。

假设餐厅第一天供应了披萨，第二天供应了汉堡，第三天又供应了披萨。那么第四天供应热狗的概率是什么呢？

其实只需要看第三天的菜单就可以了，因为马尔可夫链的特性是未来状态只与当前状态有关，与历史状态无关。所以第四天供应热狗的概率就是 0.7。

提示

需要明确的是，具有马尔可夫性并不代表这个随机过程就和历史完全没有关系。因为虽然 $t+1$ 时刻的状态只与 $t$ 时刻的状态有关，但是 $t$ 时刻的状态其实包含了 $t-1$ 时刻的状态的信息，通过这种链式的关系，历史的信息被传递到了现在。马尔可夫性可以大大简化运算，因为只要当前状态可知，所有的历史信息都不再需要了，利用当前状态信息就可以决定未来。

马尔可夫链的特点

离散时间步骤：马尔可夫链在离散的时间点上发展。
有限或可数无限状态：状态空间可以是有限的或无限的，但通常是可数的。
转移概率：从一个状态到另一个状态的概率是固定的，并且完全由当前状态决定。

马尔可夫链是随机过程的一种，但不是所有随机过程都是马尔可夫链。马尔可夫链的独特之处在于其记忆无关性（无记忆性质），即未来状态的概率分布只依赖于当前状态。

假设有一个简化的天气模型，其中只有两种状态：晴天（S）和雨天（R）。这个天气系统可以用马尔可夫链来模拟，其中每天的天气只依赖于前一天的天气。

状态空间：{晴天, 雨天}
转移概率：
- 如果今天是晴天，明天也是晴天的概率是0.8，明天变成雨天的概率是0.2。
- 如果今天是雨天，明天仍然是雨天的概率是0.6，明天变成晴天的概率是0.4。

这个过程可以用以下转移概率矩阵表示：

当前\未来	晴天	雨天
晴天	0.8	0.2
雨天	0.4	0.6

在这个例子中，如果我们知道今天的天气，我们就可以使用上表的概率来预测明天的天气。例如，如果今天是晴天，那么明天有80%的概率是晴天，20%的概率是雨天。这就是马尔可夫链的核心特性：未来状态的概率仅由当前状态决定。

随机过程是什么？

随机过程是一种数学模型，用于描述随时间变化的随机事件。在随机过程中，每一个时间点上的状态或事件都是随机的，这与确定性过程（如线性方程等）形成对比。随机过程广泛应用于各种领域，包括物理学、金融学、工程学和生物学等。

基本概念

状态空间：随机过程可能出现的所有状态的集合。
样本路径：随时间演变的一系列状态的序列，可以看作是随机过程的一个实例。
时间参数：随机过程可以是离散时间的（例如，每天的股市收盘价）或连续时间的（例如，某个粒子的位置）。

随机过程的分类

离散时间随机过程：时间参数是离散的，例如每日股价。
连续时间随机过程：时间参数是连续的，例如布朗运动。

简单的数学例子

例子：抛硬币过程

假设我们连续抛硬币，记录每次抛硬币的结果。这可以视为一个简单的随机过程。

状态空间：{正面, 反面}
时间参数：离散时间，每次抛硬币代表一个时间步。
样本路径：例如，{正面, 反面, 正面, 正面, ...}

在这个例子中，每次抛硬币的结果（状态）是随机的。如果我们假设硬币是公平的，则每次正面和反面出现的概率都是0.5。

如果用 $X_t$ 表示时间 $t$ 的硬币状态（0代表正面，1代表反面），则该随机过程可以表示为一系列随机变量 $\{X_1, X_2, ...\}$ 。每个变量 $X_t$ 都遵循相同的概率分布，即：

$P(X_t = 0) = 0.5$ （正面的概率）
$P(X_t = 1) = 0.5$ （反面的概率）

这个简单的例子就展示了随机过程的基本思想：随时间的推移，状态按照某种概率规律变化。随机过程提供了一种框架，用于研究这种随时间变化的随机现象。

马尔可夫过程的性质

由上可以总结出马尔可夫过程的三个性质：

转移概率：马尔可夫过程中，从一个状态到另一个状态的转移是由转移概率决定的。这些概率通常用转移概率矩阵来表示。
状态独立性：未来的状态仅依赖于当前的状态，不依赖于如何到达当前状态。
可预测性：虽然每个状态的转移是随机的，但整体过程的统计特性是可预测的。

假设我们有一个简化版的股市模型，其中股市的状态可以是“上涨”(U)或“下跌”(D)。这个股市模型可以用马尔可夫过程来描述，其状态转移方程如下所示。

状态空间：{上涨, 下跌}
转移概率矩阵：
- 如果今天股市上涨，明天股市继续上涨的概率是0.7，明天股市下跌的概率是0.3。
- 如果今天股市下跌，明天股市上涨的概率是0.4，明天股市下跌的概率是0.6。

转移概率矩阵可以表示为：

当前\未来	上涨	下跌
上涨	0.7	0.3
下跌	0.4	0.6

在这个模型中，未来股市的状态（上涨或下跌）完全由当天的状态决定，与之前的趋势无关。这正是马尔可夫过程的特性。

与状态转移方程的联系：在马尔可夫过程中，状态转移方程是用来描述从一个状态到另一个状态转移的概率。在上面的股市模型中，状态转移方程就是转移概率矩阵，它提供了系统从一个状态到另一个状态转移的具体概率。这种方程是马尔可夫过程分析中的关键工具，它帮助我们预测未来状态的概率分布。通过这些概率，我们可以对系统的长期行为做出预测，即使每一步的状态转移都是随机的。

马尔可夫奖励过程是什么？

马尔可夫奖励过程（Markov Reward Process，简称 MRP）是马尔可夫过程的一种扩展，它在标准马尔可夫链的基础上增加了奖励的概念，通过加入奖励元素，它允许对在随机环境中做出决策的系统进行更全面的分析。这种模型特别适用于那些需要考虑长期收益和成本的情况。

在 MRP 中，每个状态不仅有转移概率，还有与之相关联的奖励。这种模型在决策过程分析、强化学习和经济学等领域中非常有用。

马尔可夫奖励过程的组成：

状态集合：和普通的马尔可夫链一样，MRP 有一个定义明确的状态集合。
转移概率矩阵：描述从一个状态转移到另一个状态的概率。
奖励函数：为每个状态或状态转移指定一个奖励（或成本）。奖励函数通常表示为 $R(s)$ 或 $R(s, s')$ ，分别表示在状态 $s$ 获得的奖励，或从状态 $s$ 转移到状态 $s'$ 时获得的奖励。
折扣因子（ $\gamma$ ）：一个介于0和1之间的值，用于确定未来奖励的当前价值。较低的折扣因子意味着未来的奖励在当前的价值上打了折扣，即强调对即时奖励的重视。

MRP关注的是状态转移过程中的累积奖励。这种过程的目的通常是最大化某种形式的总奖励，比如长期累积奖励或折扣累积奖励。MRP通过考虑从每个状态出发的长期奖励来分析和优化决策。

假设有一个简单的游戏，游戏板上有三个状态：A、B和C。玩家从A开始，可以移动到B或C，游戏在达到C时结束。

状态集合：{A, B, C}
转移概率：
- A -> B: 0.5
- A -> C: 0.5
- B -> C: 1
- C 是吸收状态，意味着游戏结束。
奖励函数：
- A -> B: 奖励为 +5
- A -> C: 奖励为 +10
- B -> C: 奖励为 +10

在这个 MRP 中，玩家的目标是最大化从A到C的累积奖励。通过计算不同路径的预期回报，可以评估哪种策略最优。

获得回报

在马尔可夫奖励过程（MRP）中，回报是指 从一个状态到达另一个状态时获得的奖励值。它是评价决策结果好坏的关键指标。在不同的上下文中，回报可以有不同的含义，例如在游戏中可能代表得分，在金融投资中可能代表利润，在工程应用中可能代表效率的提升等。

在 MRP 中，通常关注的是累积回报，它包括从当前状态开始，未来所有步骤中获得的回报之和。如果考虑折扣因子（通常表示为 $\gamma$ ），累积回报可以表示为：

G_t = R_`{t+1}` + \gamma R_`{t+2}` + \gamma^2 R_`{t+3}` + ... = \sum_`{k=0}`^`{\infty}` \gamma^k R_`{t+k+1}`

其中 $R_{t}$ 表示在时间 $t$ 获得的回报。

初探价值函数

在马尔可夫奖励过程中，一个状态的期望回报（即从这个状态出发的未来累积奖励的期望）被称为这个状态的价值（value）。所有状态的回报就组成了价值函数（value function），价值函数的输入为某个状态，输出为这个状态的价值。

假设你计划进行一次旅行，并且有几个潜在的目的地可以选择。每个目的地都有其特有的体验和成本（或奖励）。在这个场景中，每个目的地就好比是一个“状态”，而你的决策（去哪里、做什么活动）就类似于“动作”。

状态价值函数：这可以理解为对每个目的地总体价值的评估。比如，如果选择巴黎，你可能会考虑到那里的景点、文化体验、食物等，以及这些体验的总体愉悦度（总奖励）。状态价值函数会告诉你，基于你的偏好和可能的活动，哪个目的地可能会给你带来最高的满足感（总奖励）。
动作价值函数：这不仅考虑了目的地本身的价值，还考虑了你在那里可能采取的具体活动。比如，在巴黎，你可以选择去埃菲尔铁塔（一个动作），这个选择会怎样影响你的总体旅行体验（预期奖励）。

为什么价值函数能知道每个状态的好坏？

价值函数通过估计从当前状态（或执行当前动作的状态）出发，未来可能获得的总奖励来评估状态的好坏。这通常涉及到考虑所有可能的未来路径及其奖励，并将它们折现回当前时刻。在我们的旅行例子中，这就好比是考虑到在巴黎所有可能的日程安排及其带来的快乐和成本，然后综合这些信息来评估整个旅行的价值。

价值函数和回报的关系

价值函数是对特定策略下从某个状态开始的预期累积回报的量化估计。简而言之，价值函数反映了从某个状态出发，遵循特定策略能够获得的回报总和。

回报通常指单个状态转移或一系列状态转移中获得的即时奖励。
价值函数 它通常是未来所有可能回报的加权和。

马尔可夫决策过程是什么？

马尔可夫决策过程（MDP）是马尔可夫奖励过程（MRP）的扩展，它 在 MRP 的基础上增加了决策的元素。在 MDP 中，代理需要在不同状态下做出行动的选择，从而影响状态转移和获得的奖励。因此，MDP 是解决含有决策的优化问题的强大工具。

MRP 和 MDP 的区别

马尔可夫奖励过程（MRP）:

MRP 着重于描述一个过程，其中状态的转移是随机的（决策是随机的），但不涉及决策者的选择。它包括状态集合、状态转移概率和奖励函数。
MRP 可以被看作是没有决策动作的简化版本的 MDP，即在 MRP 中，决策者不需要做出选择。

马尔可夫决策过程（MDP）:

MDP 在 MRP 的基础上增加了动作的概念。它包含状态集合、动作集合、状态转移概率（这次是依赖于所采取的动作的）、奖励函数以及有时还包括折扣因子。
MDP 考虑了决策者在不同状态下可以采取的动作，以及这些动作如何影响状态的转移和奖励。

可以发现不同于马尔可夫奖励过程，在马尔可夫决策过程中，通常存在一个智能体来执行动作。例如，一艘小船在大海中随着水流自由飘荡的过程就是一个马尔可夫奖励过程，它如果凭借运气漂到了一个目的地，就能获得比较大的奖励；如果有个水手在控制着这条船往哪个方向前进，就可以主动选择前往目的地获得比较大的奖励。

马尔可夫决策过程是一个与时间相关的不断进行的过程，在智能体和环境 MDP 之间存在一个不断交互的过程。一般而言，它们之间的交互是如图 3-3 循环过程：智能体根据当前状态 $S_t$ 选择动作 $A_t$ ；对于状态 $S_t$ 和动作 $A_t$ ，MDP 根据奖励函数和状态转移函数得到 $S_{t+1}$ $R_t$ 和并反馈给智能体。智能体的目标是最大化得到的累计奖励。智能体根据当前状态从动作的集合 $A$ 中选择一个动作的函数，被称为策略。

策略是啥？

智能体的策略（Policy）通常用字母 $\pi$ 表示。策略 $\pi(a|s) = P(A_t = a | S_t = s)$ 是一个函数，表示在输入状态 $s$ 情况下采取动作 $a$ 的概率。

当一个策略是确定性策略（deterministic policy）时，它在每个状态时只输出一个确定性的动作，即只有该动作的概率为 1，其他动作的概率为 0；
当一个策略是随机性策略（stochastic policy）时，它在每个状态时输出的是关于动作的概率分布，然后根据该分布进行采样就可以得到一个动作。

在 MDP 中，由于马尔可夫性质的存在，策略只需要与当前状态有关，不需要考虑历史状态。回顾一下在 MRP 中的价值函数，在 MDP 中也同样可以定义类似的价值函数。但此时的价值函数与策略有关，这意为着对于两个不同的策略来说，它们在同一个状态下的价值也很可能是不同的。这很好理解，因为不同的策略会采取不同的动作，从而之后会遇到不同的状态，以及获得不同的奖励，所以它们的累积奖励的期望也就不同，即状态价值不同。

假设有一个简单的场景，代理需要在两个行动（例如“向左移动”和“向右移动”）之间做出选择。以下是一个展示如何实现和应用策略的简单 Python 代码。

import numpy as np

# 定义状态空间和行动空间
states = ['状态1', '状态2', '状态3']
actions = ['向左移动', '向右移动']

# 随机策略：在每个状态下随机选择行动
def random_policy(state):
    return np.random.choice(actions)

# 确定性策略：对于每个状态，总是选择特定的行动
def fixed_policy(state):
    if state == '状态1':
        return '向右移动'
    elif state == '状态2':
        return '向左移动'
    else:
        return '向右移动'

# 测试策略
for state in states:
    action = random_policy(state)
    print(f"在 {state} 下随机策略选择的行动：{action}")

    action = fixed_policy(state)
    print(f"在 {state} 下确定性策略选择的行动：{action}")

在这个代码中，我们定义了两种策略：random_policy 是一个随机策略，它在每个状态下随机选择一个行动；fixed_policy 是一个确定性策略，它根据状态选择特定的行动。然后，我们测试这些策略在不同状态下的行动选择。

通过这种方式，策略函数指导代理在给定的状态下做出行动决策，这是强化学习中的一个关键组成部分。

在强化学习和决策理论中，策略的数学表达是用来定义在给定状态下应该采取的行动。策略可以是确定性的或随机性的。

策略的数学表达

确定性策略 可以用一个函数 $\pi$ 来表示，其中 $\pi(s)$ 表示在状态 $s$ 下应该采取的行动。数学上，它可以写作：

\pi : S \rightarrow A

这里 $S$ 是状态空间， $A$ 是行动空间。对于每个状态 $s \in S$ ， $\pi(s)$ 会返回一个明确的行动 $a \in A$ 。

随机性策略 则更复杂一些。在随机性策略中，对于每个状态 $s$ ，策略 $\pi$ 为每个可能的行动 $a$ 指定一个选择该行动的概率。因此，它可以表示为：

\pi(a|s) = P[A = a | S = s]

这里 $\pi(a|s)$ 是在状态 $s$ 下选择行动 $a$ 的概率。所有行动的概率加起来等于 1：

\sum_{a \in A} \pi(a|s) = 1, \quad \forall s \in S

例如，在一个简单的游戏中，如果有两个状态 $S = \{s_1, s_2\}$ 和两个行动 $A = \{a_1, a_2\}$ ，一个可能的随机性策略可以表示为：

$\pi(a_1|s_1) = 0.7$ , $\pi(a_2|s_1) = 0.3$
$\pi(a_1|s_2) = 0.4$ , $\pi(a_2|s_2) = 0.6$

这意味着，比如，在状态 $s_1$ 下，策略会以 70% 的概率选择行动 $a_1$ ，以 30% 的概率选择行动 $a_2$ 。

最优策略

要找到最优策略，我们需要确定在每个状态下选择哪个动作可以最大化长期奖励。这通常涉及到使用强化学习算法，比如价值迭代或策略迭代来寻找最优策略。

在之前的例子中，我们只计算了状态价值函数，这给出了在当前策略下每个状态的价值。为了找到最优策略，我们需要进行进一步的计算。我们可以使用价值迭代算法，它是一种通过反复更新状态价值函数和改善策略的方法，直到策略收敛到最优策略。

下面是一个简化的价值迭代算法的实现，用于确定最优策略：

states = ['S1', 'S2', 'S3']
actions = ['A1', 'A2']
# 状态转移概率
P = {
    ('S1', 'A1', 'S1'): 0.5, ('S1', 'A1', 'S2'): 0.5, ('S1', 'A1', 'S3'): 0.0,
    ('S1', 'A2', 'S1'): 0.0, ('S1', 'A2', 'S2'): 0.0, ('S1', 'A2', 'S3'): 1.0,
    ('S2', 'A1', 'S1'): 0.0, ('S2', 'A1', 'S2'): 0.5, ('S2', 'A1', 'S3'): 0.5,
    ('S2', 'A2', 'S1'): 0.0, ('S2', 'A2', 'S2'): 0.0, ('S2', 'A2', 'S3'): 1.0,
    ('S3', 'A1', 'S1'): 0.0, ('S3', 'A1', 'S2'): 0.0, ('S3', 'A1', 'S3'): 1.0,
    ('S3', 'A2', 'S1'): 0.0, ('S3', 'A2', 'S2'): 0.0, ('S3', 'A2', 'S3'): 1.0,
}

# 奖励函数
R = {
    ('S1', 'A1'): 1, ('S1', 'A2'): 0,
    ('S2', 'A1'): 2, ('S2', 'A2'): 0,
    ('S3', 'A1'): 0, ('S3', 'A2'): 0,
}

gamma = 0.9

V = {s: 0 for s in states}  # 初始化状态价值函数
policy = {s: actions[0] for s in states}  # 初始化策略

# 定义价值迭代函数
def value_iteration(V, policy):
    for s in states:
        # 计算每个动作的价值
        action_values = []
        for a in actions:
            action_value = R[(s, a)] + gamma * sum([P[(s, a, s_next)] * V[s_next] for s_next in states])
            action_values.append(action_value)
        
        # 选择最优动作
        best_action = actions[action_values.index(max(action_values))]
        policy[s] = best_action
        V[s] = max(action_values)

# 进行价值迭代
for _ in range(1000):  # 迭代次数
    value_iteration(V, policy)

print("最优策略:", policy)
print("状态价值函数:", V)

这个简化的价值迭代过程会逐步改善策略，直到找到每个状态的最优动作。请注意，实际应用中，状态和动作的空间可能更大，可能需要更复杂的方法和更多的迭代来找到最优策略。此外，实际的强化学习问题通常涉及更复杂的环境和策略表示。

占用度量的概念

"占用度量"（Occupancy Measure）在强化学习和其他相关领域中是一个重要概念。它描述的是智能体在其环境中行为的分布情况，具体来说，是在特定策略下智能体在各个状态（和执行各个动作）上花费时间的分布。

在强化学习中，占用度量通常定义为智能体在状态-动作空间中的访问频率。对于一个给定的策略，占用度量为每个状态-动作对分配了一个数值，这个数值表示在长期内智能体在该状态采取该动作的频率或概率。

它的主要作用：

策略评估：占用度量可以用来评估和比较不同策略的效果。通过查看智能体在特定策略下在各状态和动作上的占用情况，我们可以了解策略的行为特征。
优化和学习：在某些类型的强化学习算法中，比如策略梯度方法，占用度量可以被用来引导学习过程，帮助智能体更好地探索环境并优化其行为。
理解智能体的行为：占用度量提供了一种方式来可视化和理解智能体在环境中的行为模式，比如它更倾向于访问哪些状态，或在某些状态下倾向于采取哪些动作。

在具体的强化学习问题中，计算占用度量可能涉及到统计智能体在模拟或真实环境中的状态-动作对的访问频率。这通常需要大量的样本数据来获得准确的估计，尤其是在状态空间和动作空间很大的情况下。

虽然占用度量本身不直接是价值函数，但它与价值函数紧密相关。在强化学习中，价值函数通常表达了在给定策略下从某个状态（或状态-动作对）开始所能获得的预期回报。而占用度量则提供了智能体在这些状态和动作上花费时间的分布情况，从而间接影响到价值函数的计算和优化。

Reference

动手学强化学习-第 3 章马尔可夫决策过程

马尔可夫链是什么？​

随机过程是什么？​

马尔可夫过程的性质​

马尔可夫奖励过程是什么？​

获得回报​

初探价值函数​

价值函数和回报的关系​

马尔可夫决策过程是什么？​

MRP 和 MDP 的区别​

策略是啥？​

策略的数学表达​

最优策略​

占用度量的概念​

Reference​